/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package sorting;

import java.lang.reflect.Array;

/**
 *
 * @author Akram
 */
public final class MergeSort<T extends Comparable> extends Sort<T> {

    public MergeSort(T[] array, Class<T> classType) {
        super(array, classType);
    }

    private void divide(T[] array, int start, int end) {
        if (start < end) {
            int mid = (int) Math.floor((start + end) / 2);
            divide(array, start, mid);
            divide(array, mid + 1, end);
            mergeSubArrays(array, start, mid, end);
        }
    }

    private void mergeSubArrays(T[] array, int start, int mid, int end) {
        int sizeOfLeftArray = mid - start + 1;
        int sizeOfRightArray = end - mid;
        T[] leftArray = (T[]) Array.newInstance(classType, sizeOfLeftArray);
        T[] rightArray = (T[]) Array.newInstance(classType, sizeOfRightArray);
        for (int i = 0; i < sizeOfLeftArray; i++) {
            leftArray[i] = array[start + i];
        }
        for (int i = 0; i < sizeOfRightArray; i++) {
            rightArray[i] = array[i + mid + 1];
        }
        int i = 0, j = 0, k = 0;
        for (k = start; k <= end && i < sizeOfLeftArray && j < sizeOfRightArray; k++) {
            if (leftArray[i].compareTo(rightArray[j]) <= 0) {
                array[k] = leftArray[i++];
            } else {
                array[k] = rightArray[j++];
            }
        }
        if (i < sizeOfLeftArray) {
            for (int z = i; z < sizeOfLeftArray; z++) {
                array[k++] = leftArray[z];
            }
        }
        if (j < sizeOfRightArray) {
            for (int z = j; z < sizeOfRightArray; z++) {
                array[k++] = rightArray[z];
            }
        }
    }

    /**
     * check if array is already sorted to avoid unnecessary sorting overhead
     * @return true if array is already sorted else false
     */
    public boolean checkIfSorted() {
        boolean alreadySorted = false;
        if (array.length == 0) {
            return alreadySorted;
        }
        T element = array[0];
        for (int i = 1; i < array.length; i++) {
            if (element.compareTo(array[i]) > 0) {
                return alreadySorted;
            }
        }
        alreadySorted = true;
        return alreadySorted;
    }

    /**
     * sort the array saved in the MergeSort object
     * @param checkIfAlreadySorted will check if the array is already sorted if true by calling checkIfSorted() method
     */
    public void sort(boolean checkIfAlreadySorted) {
        if (checkIfAlreadySorted && checkIfSorted()) {
            return;
        }
        sort();
    }

    /**
     * Sort using the Merge Sort algorithm
     */
    @Override
    public void sort() {
        divide(array, 0, this.array.length - 1);
    }
}
